﻿/*
 * Bucket
 * 
 * Author: snowdreamist
 * Date: 2011/11/22
 * 
 * Bucket holds items fell in range [low, high)
 * 
 */

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using BitTorrentSharp.Maths;

namespace BitTorrentSharp.DHT
{
    public class Bucket
    {
        internal Bucket(
            DHTEngine engine,
            BigInteger low, 
            BigInteger high,
            Node[] nodes)
        {
            if (engine == null)
                throw new ArgumentNullException("engine");
            if (low == null)
                throw new ArgumentNullException("low");
            if (high == null)
                throw new ArgumentNullException("high");
            // initialize
            this.Engine = engine;
            this.Low = low;
            this.High = high;
            this.LastChangedTime = DateTime.MinValue;
            // add nodes
            if (nodes != null)
                this.InitializeAddNodes(nodes);
        }

        #region private
        /// <summary>
        /// is this a leaf bucket
        /// leaf bucket holds nodes and non-leaf bucket holds two child bucket
        /// </summary>
        private bool _isLeaf = true;
        /// <summary>
        /// sync root
        /// </summary>
        private readonly object _syncRoot = new object();
        /// <summary>
        /// Node list
        /// </summary>
        private readonly LinkedList<Node> _nodeList = new LinkedList<Node>();
        /// <summary>
        /// If this is a non-leaf bucket, then, _leftBucket represents the smaller child bucket
        /// ATTENTION
        ///     _leftBucket.High = _rightBucket.Low
        ///     And
        ///     Node with id equals to _leftBucket.High SHOULD be put in _rightBucket
        /// </summary>
        private Bucket _leftBucket;
        /// <summary>
        /// If this is a non-leaf bucket, then, _leftBucket represents the larger child bucket
        /// </summary>
        private Bucket _rightBucket;

        #region Internal core methods
        /// <summary>
        /// Add nodes on initializing
        /// </summary>
        private void InitializeAddNodes(Node[] nodes)
        {
            lock (this)
            {
                if (nodes.Length > this.Engine.Configuration.Routing.Bucket.MaxSize)
                {
                    // need split
                    this.SplitBucket(nodes);
                }
                else
                {
                    // add
                    foreach (var node in nodes)
                        this.AttachNode(node);
                }
            }
        }
        /// <summary>
        /// Internal add
        /// ATTENTION:
        ///     This method may cause a big latency since it may visit network
        /// </summary>
        private bool InternalAddNode(Node node, out Node replacedNode)
        {
            replacedNode = null;

            lock (this)
            {
                // check if exist or not
                if (this._nodeList.Contains(node))
                {
                    // exist
                    // move to end, no need to detach - attach
                    this._nodeList.Remove(node);
                    this._nodeList.AddLast(node);
                    return false;
                }
                else
                {
                    // not exist
                    // check if full or not
                    if (this.Size >= this.Engine.Configuration.Routing.Bucket.MaxSize)
                    {
                        // full
                        // check if bad node exists
                        foreach (var x in this._nodeList)
                            if (x.State == NodeState.Bad)
                            {
                                replacedNode = x;
                                break;
                            }

                        if (replacedNode != null)
                        {
                            // exist bad node
                            this.DetachNode(replacedNode);
                            this.AttachNode(node);
                            return true;
                        }
                        else
                        {
                            // no bad node exist
                            // check questionable node
                            foreach (var x in this._nodeList)
                                if (x.State == NodeState.Questionable)
                                {
                                    // ping this node!
                                    // NOTE this operation may take a while
                                    if (!x.Ping())
                                    {
                                        // a bad node
                                        replacedNode = x;
                                        break;
                                    }
                                }

                            if (replacedNode != null)
                            {
                                // exist bad node
                                this.DetachNode(replacedNode);
                                this.AttachNode(node);
                                return true;
                            }
                            else
                            {
                                // no bad node, check if split is need
                                // if Engin.CurrentNode falls into this range ,then, split into two parts
                                if (this.IsNodeFit(this.Engine.RoutingTable.CurrentNode))
                                {
                                    // fit, add to split nodes, then this node will be added
                                    this.SplitBucket(this.DetackAllNode().Concat(new Node[] { node }).ToArray());
                                    return true;
                                }
                                else
                                {
                                    // no need to add
                                    return false;
                                }
                            }
                        }
                    }
                    else
                    {
                        // not full
                        this.AttachNode(node);
                        return true;
                    }
                }
            }
        }
        /// <summary>
        /// Split bucket, generate child buckets and copy nodes, turn to non-leaf mode
        /// Auto detach nodes
        /// </summary>
        private void SplitBucket()
        {
            lock (this)
            {
                // first detach all
                var nodes = this.DetackAllNode();
                this.SplitBucket(nodes);
            }
        }
        /// <summary>
        /// Split bucket, generate child buckets and copy nodes, turn to non-leaf mode
        /// Split given nodes into new buckets
        /// </summary>
        private void SplitBucket(Node[] nodes)
        {
            if (!this._isLeaf)
                throw new InvalidOperationException("Only leaf bucket can split");

            lock(this)
            {
                // split
                BigInteger splitNumber = this.High.DividedBy2();

                Node[] leftNodes = nodes.Where(p => p.ID.BigNumber < splitNumber).ToArray();
                Node[] rightNodes = nodes.Where(p => p.ID.BigNumber >= splitNumber).ToArray();

                this._leftBucket = new Bucket(this.Engine, this.Low, splitNumber, leftNodes);
                this._rightBucket = new Bucket(this.Engine, splitNumber, this.High, rightNodes);

                this._isLeaf = false;
            }
        }
        /// <summary>
        /// Detach all
        /// </summary>
        private Node[] DetackAllNode()
        {
            lock (this)
            {
                if (this._isLeaf)
                {
                    Node[] nodes = this._nodeList.ToArray();
                    foreach (var node in nodes)
                        this.DetachNode(node);
                    return nodes;
                }
                else
                {
                    throw new InvalidOperationException("Only leaf bucket can detach nodes");
                }
            }
        }
        /// <summary>
        /// Detach node
        /// Remove event handlers
        /// Remove from list
        /// </summary>
        /// <param name="node"></param>
        private void DetachNode(Node node)
        {
            node.Pinged -= new EventHandler<PingedEventArgs>(OnNodePinged);

            lock (this)
            {
                this._nodeList.Remove(node);
                this.LastChangedTime = DateTime.Now;
            }
        }
        /// <summary>
        /// Attach node
        /// Add event handlers
        /// Add to list
        /// </summary>
        /// <param name="node"></param>
        private void AttachNode(Node node)
        {
            node.Pinged += new EventHandler<PingedEventArgs>(OnNodePinged);

            lock (this)
            {
                this._nodeList.AddLast(node);
                this.LastChangedTime = DateTime.Now;
            }
        }
        /// <summary>
        /// Internal refresh
        /// </summary>
        private void InternalRefresh()
        {
            lock (this)
            {
                foreach (var nodes in this._nodeList)
                    nodes.BeginPing(null, null);
            }
        }

        #endregion

        #region event handlers
        /// <summary>
        /// when a children node pinged
        /// </summary>
        /// <param name="sender"></param>
        /// <param name="e"></param>
        private void OnNodePinged(object sender, PingedEventArgs e)
        {
            // update last changed time
            this.LastChangedTime = DateTime.Now;
        }

        #endregion

        #endregion

        #region properties
        /// <summary>
        /// DHT Engine
        /// </summary>
        public DHTEngine Engine { get; private set; }
        /// <summary>
        /// Current size
        /// </summary>
        public int Size
        {
            get
            {
                if (this._isLeaf)
                    return this._nodeList.Count;
                else
                    return this._leftBucket.Size + this._rightBucket.Size;
            }
        }
        /// <summary>
        /// Low boundary
        /// </summary>
        public BigInteger Low { get; private set; }
        /// <summary>
        /// High boundary
        /// </summary>
        public BigInteger High { get; private set; }
        /// <summary>
        /// Last changed time
        /// </summary>
        public DateTime LastChangedTime { get; private set; }

        #endregion

        #region basic operations
        /// <summary>
        /// Add node
        /// </summary>
        /// <param name="node"></param>
        internal bool AddNode(Node node, out Node replacedNode)
        {
            lock (this)
            {
                if (this.IsNodeFit(node))
                {
                    if (this._isLeaf)
                    {
                        // leaf
                        return this.InternalAddNode(node, out replacedNode);
                    }
                    else
                    {
                        // non-leaf
                        if (node.ID.BigNumber < this._leftBucket.High)
                        {
                            // fall into left child
                            return this._leftBucket.AddNode(node, out replacedNode);
                        }
                        else
                        {
                            // fall into right child
                            return this._rightBucket.AddNode(node, out replacedNode);
                        }
                    }
                }
                else
                {
                    throw new ArgumentOutOfRangeException("node.ID should fall into range [Low, high)");
                }
            }
        }
        /// <summary>
        /// add nodes
        /// </summary>
        /// <param name="nodes">All nodes need to add</param>
        /// <param name="notAddedNodes">The nodes not added</param>
        /// <param name="replacedNodes">The nodes has been removed</param>
        internal void AddNodes(Node[] nodes, out Node[] notAddedNodes, out Node[] replacedNodes)
        {
            List<Node> notAddedNodeList = new List<Node>();
            List<Node> replacedNodeList = new List<Node>();

            foreach (var node in nodes)
            {
                Node replacedNode;
                // add
                if (this.AddNode(node, out replacedNode))
                    replacedNodeList.Add(replacedNode);
                else
                    notAddedNodeList.Add(node);
            }

            notAddedNodes = notAddedNodeList.ToArray();
            replacedNodes = replacedNodeList.ToArray();
        }
        /// <summary>
        /// Refresh nodes
        /// </summary>
        /// <param name="autoClean">remove bad nodes or not</param>
        internal void Refresh(bool autoClean = false)
        {
            lock (this)
            {
                if (this._isLeaf)
                {
                    this.InternalRefresh();
                }
                else
                {
                    this._leftBucket.Refresh();
                    this._rightBucket.Refresh();
                }
            }
        }
        /// <summary>
        /// Is node fit in this range
        /// </summary>
        public bool IsNodeFit(Node node)
        {
            if (node == null)
                throw new ArgumentNullException("node");

            return node.ID.BigNumber >= this.Low && node.ID.BigNumber < this.High;
        }

        #endregion

        #region event

        #endregion
    }
}
